package com.leecode.xiehf.page_01;

/**
 * 给你一个只包含 '(' 和 ')' 的字符串，找出最长有效（格式正确且连续）括号子串的长度。
 * <p>
 * https://leetcode-cn.com/problems/longest-valid-parentheses/
 */
public class Solution_0032 {

    public static void main(String[] args) {
        Solution_0032 solution = new Solution_0032();
        int result = solution.longestValidParentheses("()(()())))))");
        System.out.println(result);
    }

    /**
     * 动态规划的问题
     * 从i= 1 开始 该位置是有效的括号的前提是 s.charAt(i)=')'  却前面i-2为止也是有效地
     * @param s
     * @return
     */
    public int longestValidParentheses(String s) {
        if (s.length() <= 1) {
            return 0;
        }
        int max = 0;
        int[] dp = new int[s.length()];
        for (int i = 1; i < s.length(); i++) {
            if (s.charAt(i) == ')') {
                if (s.charAt(i - 1) == '(') {
                    if (i >= 2) {
                        dp[i] = dp[i - 2] + 2;
                    } else {
                        dp[i] = 2;
                    }
                } else {
                    if (dp[i - 1] > 0) {
                        int index = i - dp[i - 1] - 1;
                        if (index >= 0) {
                            if (s.charAt(index) == '(') {
                                dp[i] = dp[i - 1] + 2;
                                // -------------------------

                                // i - dp[i - 1] - 2
                                //    |
                                // (  ) ( ( ............. )  )
                                //      |                 |  |
                                //      |                 |  i
                                // i - dp[i - 1] - 1    i-1

                                //-------------------------
                                if (i - dp[i - 1] - 2 > 0) {
                                    dp[i] = dp[i] + dp[i - dp[i - 1] - 2];
                                }
                            }
                        }
                    }
                }
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }

        /**
         * 答案一定是偶数
         *
         * @param s
         * @return
         */
    public int longestValidParentheses1(String s) {
        int max = 0;
        for (int i = 0; i < s.length() - max; i++) {
            if (s.charAt(i) != '(') {
                continue;
            }
            // 从i开始检查是否为有效的
            max = Math.max(max, getMax(s, i));
        }
        return max;
    }

    private int getMax(String s, int start) {
        int index = start;
        int sum = 0;
        int max = 0;
        while (index < s.length()) {
            char left = s.charAt(index);
            if (left == '(') {
                sum++;
            } else {
                sum--;
                if (sum == 0) {
                    max = index - start + 1;
                }
            }
            if (sum < 0) {
                break;
            }
            index+=1;
        }
        return max;
    }
}

